/**
 * 图数据结构的实现类，用于存储和操作图形结构。
 */
package com.game.comment.util;

import com.game.comment.exection.ServiceException;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.*;

public class Graph {
    private final Map<Integer, Set<Integer>> adjList;    // 使用set 可以去重
    public Graph() {
        adjList = new HashMap<>();
    }

    // 单向
    public void oneWayAddEdge(Integer source, Integer target) {
        adjList.computeIfAbsent(source, k -> new HashSet<>()).add(target);
    }

    // 双向
    public void twoWayAddEdge(Integer source, Integer target) {
        adjList.computeIfAbsent(source, k -> new HashSet<>()).add(target);
        adjList.computeIfAbsent(target, k -> new HashSet<>()).add(source);
    }
    // 这里必须保证 start和end 都在图中
    public Set<Set<Node>> bfsAllPaths(Integer start, Integer end) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> parent = new HashMap<>();
        Set<Set<Node>> lists = new LinkedHashSet<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            // //遍历当前节点相邻的所有节点 //判断访问过的话记录路径的话去的是最少节点
            for (int neighbor : adjList.getOrDefault(current, Collections.emptySet())) {
                if (neighbor == end) {// 如果当前邻居节点是终点
                    parent.put(neighbor, current); // 记录路径
                    List<Integer> path = new ArrayList<>();
                    for (int step = end; step != start; step = parent.get(step)) {
                        path.add(step);
                    }
                    path.add(start);
                    Collections.reverse(path);// 自然顺序反排
                    Set<Node> set =  new HashSet<>();
                    for (int i = 0; i < path.size()-1; i++) {
                        Node node = new Node(path.get(i), path.get(i + 1), 0);
                        set.add(node);
                    }
                    lists.add(set);
                }else if (!parent.containsKey(neighbor)){
                    parent.put(neighbor, current); // 记录路径
                    queue.add(neighbor);          // 将该节点加入队列
                }
            }
        }
        return lists; // 没有找到路径
    }
    public List<Node> bfsMinPaths(Integer start, Integer end) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> parent = new HashMap<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (current == end) {// 如果当前节点是终点
                List<Integer> path = new ArrayList<>();
                for (int step = end; step != start; step = parent.get(step)) {
                    path.add(step);
                }
                path.add(start);
                Collections.reverse(path);// 自然顺序反排

                List<Node> list = new ArrayList<>();
                for (int i = 0; i < path.size()-1; i++) {
                    Node node = new Node(path.get(i), path.get(i + 1), 0);
                    list.add(node);
                }
                return list;
            }
            // //遍历当前节点相邻的所有节点 //判断访问过的话记录路径的话去的是最少节点
            for (int neighbor : adjList.getOrDefault(current, Collections.emptySet())) {
                if (!parent.containsKey(neighbor)) {
                parent.put(neighbor, current); // 记录路径
                queue.add(neighbor);          // 将该节点加入队列
                }
            }
        }
        throw new ServiceException("无可用路径");
    }
}

